public class prog {
    //
//import java.util.Scanner;
//import java.io.IOException;
//import java.util.Random;
//public class prog {public static int add(int n){
//    if(n>1){
//        return n*add(n-1);
//    }
//    return n;
//}
//    public static void main(String[]args){
//        Scanner scan =new Scanner(System.in);
//        int n=scan.nextInt();
//        System.out.println(add(n));
//    }
//}
//
//
//
//
//
//
//
//
//import java.util.Scanner;
//import java.io.IOException;
//import java.util.Random;
//public class prog {public static int add(int n){
//    if(n!=0){
//        return n+add(n-1);
//    }
//    return n;
//}
//    public static void main(String[]args){
//        Scanner scan =new Scanner(System.in);
//        int n=scan.nextInt();
//        System.out.println(add(n));
//    }
//}
//
//
//
//
//
//
//
//import java.util.Scanner;
//import java.io.IOException;
//import java.util.Random;
//public class prog {public static void add(int n){
//    if(n>9){
//        add(n/10);
//    }
//    System.out.println(n%10);
//}
//    public static void main(String[]args){
//        Scanner scan =new Scanner(System.in);
//        int n=scan.nextInt();
//        add(n);
//    }
//}
//
//
//
//
//
//
//
//
//
//import java.util.Scanner;
//import java.io.IOException;
//import java.util.Random;
//public class prog {public static int add(int n){
//    if(n<10){
//        return n;
//    }
//    return n%10+add(n/10);
//}
//    public static void main(String[]args){
//        Scanner scan=new Scanner(System.in);
//        int n=scan.nextInt();
//        int ret=add(n);
//        System.out.println(ret);
//    }
//}
//
//
//
//
//
//
//
//
//import java.util.Scanner;
//import java.io.IOException;
//import java.util.Random;
//public class prog {
//    public static int jump(int n){
//        if(n==1) {
//            return 1;
//        }
//        if(n==2){
//            return 2;
//        }
//        if(n==0){
//            return 0;
//        }
//        return jump(n-1)+jump(n-2);
//    }
//    public static void main(String[]args){
//        Scanner scan=new Scanner(System.in);
//        int n=scan.nextInt();
//        int ret=jump(n);
//        System.out.println(n+"阶台阶有："+ret+"种跳法");
//    }
//}
//
//
//
//
//
//
//
//import java.util.Scanner;
//import java.io.IOException;
//import java.util.Random;
//public class prog {public static double add(double c,double d,double e){
//    return (c+d+e);
//}
//    public static int add(int a,int b){
//        return (a+b);
//    }
//    public static void main(String[]args){
//        Scanner scan=new Scanner(System.in);
//        int a=scan.nextInt();
//        int b=scan.nextInt();
//        System.out.println("两个正数和为："+add(a,b));
//        double c = scan.nextDouble();
//        double d = scan.nextDouble();
//        double e = scan.nextDouble();
//        System.out.println("三个小数的和为："+add(c,d,e));
//    }
//}
//
//
//
//
//
//
//
//
//
//import java.util.Scanner;
//import java.io.IOException;
//import java.util.Random;
//public class prog {public static int max(int x,int y) {
//    return x>y?x:y;
//}
//    public static double max(double x,double y){
//        return x>y?x:y;
//    }
//    public static void main(String[]args){
//        Scanner scan=new Scanner(System.in);
//        int a=scan.nextInt();
//        int b=scan.nextInt();
//        System.out.println("两个数最大是："+max(a,b));
//        double c=scan.nextDouble();
//        double d=scan.nextDouble();
//        System.out.println("两个小数最大的是："+max(c,d));
//    }
//}
//
//
//
//
//
//
//
//
//
//import java.util.Scanner;
//import java.io.IOException;
//import java.util.Random;
//public class prog {public static int max3(int n1,int n2,int n3){
//    return max2(max2(n1,n2),n3);
//}
//    public static int max2(int n1,int n2){
//        return n1>n2?n1:n2;
//    }
//    public static void main(String[]args){
//        Scanner scan=new Scanner(System.in);
//        int n1=scan.nextInt();
//        int n2=scan.nextInt();
//        int n3=scan.nextInt();
//        int ret=max3(n1,n2,n3);
//        System.out.println("最大数为："+ret);
//    }
//}
//
//
//
//
//
//
//
//
//
//import java.util.Scanner;
//import java.io.IOException;
//import java.util.Random;
//public class prog {
//    public static void main(String[]args){
//        int[] arr={1,2,3,4,5,6,7,8,9,10};
//        int i=0;
//        int j=arr.length-1;
//        int tmp=0;
//        while(i<j){
//            while(arr[i]%2==1&&i<j){
//                i++;
//            }
//            while(arr[j]%2==0&&i<j){
//                j--;
//            }
//            tmp=arr[i];
//            arr[i]=arr[j];
//            arr[j]=tmp;
//        }
//        for(int k=0;k<arr.length;k++)
//        {
//            System.out.print(arr[k]+" ");
//        }
//    }
//}
//
//
//
//
//
//
//
//
//import java.util.Scanner;
//import java.io.IOException;
//import java.util.Random;
//public class prog {public static void main(String[]args){
//    Scanner scan=new Scanner(System.in);
//    int n=scan.nextInt();
//    int count=1;
//    for(int i=1;i<=n;i++){
//        count*=i;
//    }
//    System.out.println(n+"的阶乘为："+count);
//}
//}
//
//
//
//
//
//
//
//
//import java.util.Scanner;
//import java.io.IOException;
//import java.util.Random;
//public class prog {
//    public static void main(String[]args){
//        Scanner scan=new Scanner(System.in);
//        int n=scan.nextInt();
//        int count=0;
//        int sum=0;
//        for(int i=0;i<n;i++){
//            sum=1;
//            for(int j=1;j<=n-i;j++){
//                sum*=j;
//            }
//            count+=sum;
//        }
//        System.out.println("总和为："+count);
//    }
//}
//
//
//
//
//
//
//
//
//import java.util.Scanner;
//import java.io.IOException;
//import java.util.Random;
//public class prog {public static void main(String[]args){
//    int sum1=0;
//    int sum2=1;
//    int tmp=0;
//    Scanner scan=new Scanner(System.in);
//    int n=scan.nextInt();
//    int x=n;
//    while(n>2){
//        tmp=sum1+sum2;
//        sum1=sum2;
//        sum2=tmp;
//        n--;
//    }
//    System.out.println("第"+x+"位斐波那契额数为："+tmp);
//}
//}
//
//
//
//
//
//
//
//
//import java.util.Scanner;
//import java.io.IOException;
//import java.util.Random;
//public class prog {
//    public static void main(String[]args){
//        int[] arr={1,2,3,4,5,6,5,4,6,3,1};
//        int n=arr[0];
//        for(int i=1;i<arr.length;i++){
//            n^=arr[i];
//        }
//        System.out.println(n);
//    }
//}
//
//
//
//
//
//
//
//
//public class prog {public static void main(String[]args){
//    for(int i=1;i<=9;i++){
//        for(int j=1;j<=i;j++){
//            System.out.print( i+" * "+j+" ="+(i*j) +"  ");
//        }
//        System.out.println();
//    }
//}
//}
//
//
//
//
//
//
//
//
//import java.util.Scanner;
//import java.io.IOException;
//import java.util.Random;
//
//public class prog {public static void print(int x,int tmp){
//    if(x>9){
//        print(x/10,tmp);
//    }
//    System.out.print(x%10+" ");
//    if(x!=tmp){
//        System.out.print(",");
//    }
//}
//    public static void main(String[]args){
//        int x=123;
//        int tmp=x;
//        print(x,tmp);
//    }
//}
//
//
//
//
//
//
//
//
//
//import java.util.Scanner;
//import java.io.IOException;
//import java.util.Random;
//public class prog {
//    public static void main(String[]args){
//        Scanner scan = new Scanner(System.in);
//        int count=3;
//        while(count != 0){
//            String password=scan.nextLine();
//            if(password.equals("zhang")){
//                System.out.println("输入正确");
//                break;
//            }
//            count--;
//            System.out.println("还有"+count+"次机会");
//        }
//    }
//
//
//
//
//
//
//
//
//
//import java.util.Scanner;
//import java.io.IOException;
//import java.util.Random;
//public class prog {
//    public static void main(String[]args){
//        Scanner scan=new Scanner(System.in);
//        int n=scan.nextInt();
//        for(int i=31;i>=1;i-=2){
//            System.out.print(n>>i&1);
//        }
//        System.out.println();
//        for(int i=30;i>=0;i-=2){
//            System.out.print(n>>i&1);
//        }
//    }
//}
//
//
//
//
//
//
//
//
//import java.util.Scanner;
//import java.io.IOException;
//import java.util.Random;
//public class prog {
//    public static void main(String[]args){
//        Scanner scan=new Scanner(System.in);
//        int n=scan.nextInt();
//        int count=0;
//        while(n!=0){
//            count++;
//            n&=n-1;
//        }
//        System.out.println(count);
//    }
//}
//
//
//
//
//
//
//
//
//
//import java.util.Scanner;
//import java.io.IOException;
//import java.util.Random;
//public class prog {public static void main(String[]args){
//    Scanner scan=new Scanner(System.in);
//    int n=scan.nextInt();
//    int x=scan.nextInt();
//    if(n>x){
//        int tmp=n;
//        n=x;
//        x=tmp;
//    }
//    for(int i=n;i>=1;i--){
//        if(x%i==0&&n%i==0){
//            System.out.println("最大公约数为："+i);
//            break;
//        }
//    }
//}
//}
//
//
//
//
//
//
//
//
//public class prog {
//    public static void main(String[]args){
//        double sum=0;
//        for(int i=1;i<=100;i++){
//            if(i%2==0){
//                sum-=1.0/i;
//            }
//            else if(i%2==1){
//                sum+=1.0/i;
//            }
//        }
//        System.out.println(sum);
//    }
//}
//
//
//
//
//
//
//
//
//
//
//public class prog {
//    public static void main(String[]args){
//        for(int i=2;i<1000;i++){
//            int g=i%10;
//            int s=i/10%10;
//            int b=i/100;
//            if(i==(g*g*g+s*s*s+b*b*b)){
//                System.out.println(i);
//            }
//        }
//    }
//}
//
//
//
//
//
//
//
//
//
//import java.util.Scanner;
//import java.io.IOException;
//import java.util.Random;
//public class prog {public static void main(String[]args){
//    Random random=new Random();
//    int rand=random.nextInt(100)+1;
//    while(true){
//        Scanner scan=new Scanner(System.in);
//        int n=scan.nextInt();
//        if(n==rand){
//            System.out.println("回答正确");
//            break;
//        }
//        else if(n<rand){
//            System.out.println("小了");
//        }
//        else{
//            System.out.println("大了");
//        }
//    }
//}
//}
//
//
//
//
//
//
//
//import java.util.Scanner;
//public class prog {
//    public static void main(String[]args){
//        Scanner scan=new Scanner(System.in);
//        int n=scan.nextInt();
//        for(int i=0;i<n;i++){
//            for(int j=0;j<n;j++){
//                if(i==j){
//                    System.out.print("*");
//                }
//                else if(j==n-i-1){
//                    System.out.print("*");
//                }
//                else{
//                    System.out.print(" ");
//                }
//            }
//            System.out.print("\n");
//        }
//    }
//}
//
//
//
//
//
//
//
//
//import java.util.Scanner;
//public class prog {
//    public static void main(String[]args){
//        Scanner scan=new Scanner(System.in);
//        int a=scan.nextInt();
//        if(a<19){
//            System.out.println("少年");
//        }
//        else if(a>18&&a<29){
//            System.out.println("青年");
//        }
//        else if(a>28&&a<56){
//            System.out.println("中年");
//        }
//        else{
//            System.out.println("老年");
//        }
//    }
//}
//
//
//
//
//
//
//
//
//import java.util.Scanner;
//public class prog {
//    public static void main(String[]args){
//        Scanner scan=new Scanner(System.in);
//        int a=scan.nextInt();
//        int flase=1;
//        for(int i=a-1;i>1;i--){
//            if(a%i==0){
//                flase=0;
//                break;
//            }
//        }
//        if(flase==1){
//            System.out.println(a+"是素数");
//        }
//        else{
//            System.out.println(a+"不是素数");
//        }
//    }
//}
//
//
//
//
//
//
//
//
//public class prog {
//    public static void main(String[]args){
//        for(int i=2;i<=100;i++){
//            int flase=1;
//            for(int j=i-1;j>1;j--){
//                if(i%j==0){
//                    flase=0;
//                    break;
//                }
//            }
//            if(flase!=0){
//                System.out.println(i);
//            }
//        }
//    }
//}
//
//
//
//
//
//
//public class prog {
//    public static void main(String[]args){
//        int count=0;
//        for(int i=1;i<100;i++){
//            if(i%10==9){
//                count++;
//            }
//            if(i/10==9){
//                count++;
//            }
//        }
//        System.out.println(count);
//    }
//}
//
//
//
//
//
//
//public class prog {
//    public static void main(String[]args){
//        for(int i=1000;i<2000;i++){
//            if(i%4==0&&i%100!=0||i%400==0){
//                System.out.println(i);
//            }
//        }
//    }
//}
}
